import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class Solver {

    private Map<Board, Board> s = new HashMap<Board, Board>();

    private MinPQ<Board> pq1 = new MinPQ<Board>(new Comparator<Board>() {
        @Override
        public int compare(Board o1, Board o2) {
            return o1.manhattan() - o2.manhattan();
        }
    });
    private MinPQ<Board> pq2 = new MinPQ<Board>(new Comparator<Board>() {
        @Override
        public int compare(Board o1, Board o2) {
            return o1.manhattan() - o2.manhattan();
        }
    });
    private LinkedList<Board> solution = new LinkedList<Board>();

    public Solver(Board initial) {
        this.pq1.insert(initial);
        this.pq2.insert(initial.twin());
        while (true) {
            Board b1 = this.pq1.delMin();
            Board b2 = this.pq2.delMin();
            if (b1.isGoal()) {
                do {
                    solution.addFirst(b1);
                    b1 = s.get(b1);
                } while (b1 != null);
                break;
            }
            if (b2.isGoal()) {
                break;
            }
            for (Board n1 : b1.neighbors()) {
                this.pq1.insert(n1);
                this.s.put(n1, b1);
            }
            for (Board n2 : b2.neighbors()) {
                this.pq2.insert(n2);
            }
        }
    }

    public boolean isSolvable() {
        return !this.solution.isEmpty();
    }

    public int moves() {
        return this.solution.size() - 1;
    }

    public Iterable<Board> solution() {
        return this.solution;
    }

//    private static int[][] buildRandom(int N, int steps) {
//        int k = 1;
//        int[][] blocks = new int[N][N];
//        for (int i = 0; i < N; i++) {
//            for (int j = 0; j < N; j++) {
//                blocks[i][j] = k++;
//            }
//        }
//        blocks[N - 1][N - 1] = 0;
//
//        Random r = new Random();
//        Board b = new Board(blocks);
//        for (int s = 0; s < steps; s++) {
//            List<Board> neighbors = (List<Board>) b.neighbors();
//            b = neighbors.get(r.nextInt(neighbors.size()));
//        }
//
//        return b.getBlocks();
//    }

    public static void main(String[] args) {
        // create initial board from file
        In in = new In(args[0]);
        int N = in.readInt();
        int[][] blocks = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                blocks[i][j] = in.readInt();
        Board initial = new Board(blocks);

        // solve the puzzle
        Solver solver = new Solver(initial);

        // print solution to standard output
        if (!solver.isSolvable())
            StdOut.println("No solution possible");
        else {
            StdOut.println("Minimum number of moves = " + solver.moves());
            for (Board board : solver.solution())
                StdOut.println(board);
        }
    }

}
